package com.amos.stuff.leetcode.sumoftwonumber;

import java.util.HashMap;
import java.util.Map;

/**
 * Copyright © 2018 五月工作室. All rights reserved.
 *
 * @Package com.amos.stuff.leetcode.sumoftwonumber
 * @ClassName SumOfTwoNumbers
 * @Description 两数之和
 * ***************************************************************
 * 题目描述：
 * 给定一个整数数组 nums 和一个目标值 target, 请你在该数组中找出和为目标值的那两个 整数，并返回数组下标
 * <p>
 * 备注要求：
 * 你可以假设每种输入只会对应一个答案，但是，你不能重复利用这个数组中同样的元素
 * <p>
 * 示例说明：
 * nums = [2,4,5,6,8,9], target = 10
 * 因为 2 + 9 = 11 = target
 * 所以返回： [0,5]
 * <p>
 * 分析：
 * 两个数组元素之和等于target，那么符合条件的可能不值一对，可能是多个；
 * 现在看备注要求，每种输入只会有一种答案，这里的一个答案有点歧义，我们可以这么理解:
 * 1）一个答案里面只能有一个对符合条件的数组元素
 * 2）一个答案里面可能有多对符合条件的数组元素
 * <p>
 * 这样的话，就有歧义了，但是所幸的是备注要求里面还有第二个要求，不能重复利用这个数组中的同样的元素，
 * 这在我理解为对所给个nums有要求了，所给的数组中，要求有且只有两个数组元素的和等于target
 * <p>
 * 最粗暴的做法是：双重循环该数组，然后两个数组相加的值等于target 则将两个数组元素的下表返回，这种做法循环的次数为 n * n ，
 * 好处是 如果变更了 备注要求则可以简单的讲返回数组下标的数据结构变更下即可满足要求
 * 坏处是 时间复杂段太高了
 * <p>
 * leetcode官方优化：
 * 使用HashMap来将迭代，并将元素插入到Map中，与此同时计算目标值与当前数组元素的差值是否存在数组中，如果存在则直接返回两个数组下标，如果不存在则记录该数组元素
 * HashMap的key是数组元素，value是数组元素的下标
 * <p>
 * 我们将展示两种方法
 * ***************************************************************
 * @Author Amos
 * @Modifier
 * @Date 2019/10/27 21:35
 * @Version 1.0
 **/
public class SumOfTwoNumbers {
    /**
     * 方法一：直接暴力双重for循环
     *
     * @param nums   目标数组
     * @param target 目标值
     * @return
     */
    public static int[] directForeach4SumOfTwoNumbers(int[] nums, int target) {
        int[] valueArr = null;
        long startTime = System.currentTimeMillis();
        for (int i = 0, len = nums.length; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (nums[j] == target - nums[i]) {
                    valueArr = new int[]{i, j};
                }
            }
        }
        System.out.println("方法一消耗时间：" + (System.currentTimeMillis() - startTime));
        return valueArr;
    }

    /**
     * 方法二：使用HashMap来匹配
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] hashMap4SumOfTwoNumbers(int[] nums, int target) {
        int[] valueArr = null;
        long startTime = System.currentTimeMillis();

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0, len = nums.length; i < len; i++) {

            int value = target - nums[i];
            if (map.containsKey(value)) {
                valueArr = new int[]{map.get(value), i};
            }
            map.put(nums[i], i);
        }
        System.out.println("方法二消耗时间：" + (System.currentTimeMillis() - startTime));

        return valueArr;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 0};
        int target = 9;
        int[] arr1 = directForeach4SumOfTwoNumbers(nums, target);
        int[] arr2 = hashMap4SumOfTwoNumbers(nums, target);
        System.out.println(arr1 == null ? "没有匹配数据" : arr1[0] + "," + arr1[1]);
        System.out.println(arr2 == null ? "没有匹配数据" : arr2[0] + "," + arr2[1]);

    }

}
